package sorting;

import java.util.Arrays;

import util.ArrayUtil;
import util.MathUtil;

public class HoareQuickSort {
	public static void sort(float[] numbers, int l, int r) throws InterruptedException
	{
		if(l >= r) return;

		if(r - l > 1)
		{
			ArrayUtil.each(numbers, r, MathUtil.random(l, r));

			int pivotIndex = partition(numbers, l, r);
	
			sort(numbers, l, pivotIndex);
			sort(numbers, pivotIndex + 1, r);
		}
		else if(numbers[l] > numbers[r])
		{
			ArrayUtil.each(numbers, r, l);
		}
	}
	
	private static int partition(float[] numbers, int l, int r) throws InterruptedException
	{
		float pivotValue = numbers[r];
		
		int i = l - 1, j = r + 1;
		while(true)
		{
			do j --;
			while(numbers[j] > pivotValue);

			do i ++;
			while(numbers[i] < pivotValue);

			if(i >= j)
				return j;

			if(numbers[i] != numbers[j])
				ArrayUtil.each(numbers, i, j);
		}
	}
	
	public static void main(String[] args) throws InterruptedException {
		float[] numbers = {1, 4, 2, 7, 8, 3, 5, 6, 10, 9, 10, 8};
		sort(numbers, 0, numbers.length - 1);
		
		System.out.println(Arrays.toString(numbers));
	}
}
